package com.mj;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

import com.mj.AVLTree.AVLNode;
import com.mj.printer.BinaryTreeInfo;


public class BinaryTree<E> implements BinaryTreeInfo {
	protected int size;
	protected Node<E> root;
	private Comparator<E> comparator;

	public BinaryTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		root = null;
		size = 0;
	}

	public boolean contains(E element) {
		return false;
	}

	public int height() {
		int levelSize = 1;
		int height = 0;
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			levelSize--;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
			if (levelSize == 0) {
				height++;
				levelSize = queue.size();
			}
		}
		return height;
	}
	
    public Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}
		Node<E> p = node.left;
		if (p != null) {
			while (p.right != null) {
				p= p.right;
			}
			return p;
		}
		
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}
		
		return node.parent;
	}
	
	public Node<E> createNode(E element, Node<E> parent) {
		return new Node<>(element, parent);
	}
	
	public static class Node<E> {
		public E element;
		public Node<E> left;
		public Node<E> right;
		public Node<E> parent;

		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
		
		public Boolean isLeftChild() {
			return this.parent != null && this == this.parent.left;
		}
		
		public Boolean isRightChild() {
			return this.parent != null && this == this.parent.right;
		}
	}

	public void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}

	@SuppressWarnings("unchecked")
	public int compare(E e1, E e2) {
		if (comparator == null) {
			return ((Comparable<E>) e1).compareTo(e2);
		}
		return comparator.compare(e1, e2);
	}

	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return root;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>) node).left;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>) node).right;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
		AVLNode<E> myNode = (AVLNode<E>)node;
		String parentString = "null";	
		if (myNode.parent != null) {
			parentString = myNode.parent.element.toString();
		}
		return myNode.element + "_p(" + parentString + ")" + "_h(" + myNode.height + ")";			
	}
}
